#include<stdio.h>
#include<malloc.h>
#include<string.h>

//2.1 树结构体实现
#define NAMESIZE 20           //节点名称长度
typedef char NODE[NAMESIZE];  //节点名称类型NODE，存储节点名称

typedef struct BROTHERNODE   //兄弟节点类型，表示兄弟关系
{
    NODE node;               //兄弟节点名称
    struct BROTHERNODE *next;//兄弟节点链接指针，链接其他兄弟
}BROTHERNODE,*BROTHER;       //重命名兄弟节点类型,BROTHER为指向BROTHERNODE的指针

typedef struct PARENTNODE     //双亲节点类型，表示子树树根节点
{
    NODE node;                //双亲节点名称              
    BROTHER children;         //所有子节点
}PARENT;                      //重命名双亲节点类型，PARENT为PARENTNODE的代名

typedef struct TREENODE       //树分支节点类型
{
    PARENT node;              //双亲节点，表示子树的树根节点
    struct TREENODE *next;    //双亲节点指针指向其他双亲节点
}TREENODE,*TREE;              //重命名树分支节点类型，TREE为指向TREENODE的指针

//2.2 树存储实现
/*
//2.2.1 通用比较函数
int Equal(NODE n1,NODE n2, int *fun())
{
    return (int)fun(n1,n2);
}//判断树的两个节点是否相同，若相同则为1，否则则为0

//2.2.2 通用赋值函数
void Set (NODE n1,NODE n2,void *fun())
{
    fun(n1,n2);
}
*/

//2.2.3 兄弟节点关系的构建
BROTHER Add_A_Brother(BROTHER br,NODE node)        //Add_A_Brother把一个节点加入到兄弟节点群中
{
    BROTHER b,pb;                                  //兄弟节点
    b=(BROTHER)malloc(sizeof(struct BROTHERNODE)); //动态开辟一个兄弟节点
    //Set(b->node,node,node,SteValue);             //【下面两行是类型为str时的情况，其他类比】
    strcpy(b->node,node);
    b->next=NULL;
    if(br==NULL)                                    //没有兄弟节点的情况
    {
        br=b;                                       //node就是第一个兄弟
    }
    else                                            //有兄弟节点的情况
    {
        pb=br;                                      //node就是最后一个兄弟节点【值在b中，头插入】
        while(pb->next)   pb=pb->next;
        pb->next=b;
    }
    return br;                                      //返回兄弟节点【指针】
}

//2.2.4 双亲与子节点关系的构建
TREE Form_Pa_Ch(NODE pa,BROTHER br)                 //将兄弟节点(所有子节点)链接到双亲节点中，构成一个子树
{
    TREE parent;
    parent=(TREE)malloc(sizeof(struct TREENODE));   //创建双亲节点
    //Set(parent->node.node,pa,Setvalue)
    strcpy(parent->node.node,pa);
    parent->next=NULL;
    parent->node.children=br;                       //兄弟节点与双亲节点构成子树
    return parent;                                  //返回带兄弟节点的双亲结点，即子树
}

//2.2.5 将带子节点的双亲节点加入到树中
TREE Add_A_Sub_Tree(TREE tree,TREE subtree) //将双亲结点加入到树中
{
    TREE t=tree;                        //临时树
    if(tree==NULL)                      //树不存在
    {
        tree=subtree;                   //带子节点的双亲节点即为树
    }
    else                                //树存在
    {
        while(t->next)  t=t->next;
        t->next=subtree;                //带子节点的双亲节点加入到树的最后
    }
    return tree;                        //返回树指针
}//tree是链式队列，通过上述程序实现子树subtree(双亲结点)进队列过程

//2.2.6 清除兄弟节点和树
BROTHER ClearBrothers(BROTHER br)  //回收兄弟节点空间
{
    BROTHER br1=br;                //临时兄弟变量
    while(br)                      //【遍历兄弟节点】
    {
        br1=br;
        br=br->next;               //【挨个变量赋给临时指针】
        free(br1);                 //回收单元
        return br;
    }
    return br;                     //返回NULL
}

//2.2.7 清空树并回收数据单元
TREE ClearTree(TREE tree)
{
    TREE tree1=tree;              //临时树
    while(tree)                   //【遍历双亲节点】
    {
        tree1=tree;
        tree=tree->next;          //【挨个变量赋给临时指针】
        free(tree1);              //回收单元
    }
    return tree;
}//在程序运行结束前需要动态回收动态开辟的数据单元
//以上两个程序实际上是出队列过程，只是没有返回值

//2.2.8 字符数值转换
//把字符串的字符'/'转换为转义字符'\0'(字符串结束标志)，故需要在字符串数组中存放多个节点名称(兄弟节点)的字符串
void CreateStr(char *brotherset)  //字符数组转换为多个字符串
{
    char *c=brotherset;           //临时字符串
    while(*c)
    {
        if(*c=='/')  *c='\0';     //插入字符串结束标志
        c++;
    }
    c++;
    *c='\0';                      //多一个结束标记
}

//2.2.9 字符数组建立兄弟关系
//把字符串数组中的多个兄弟节点节点名称建立成树的兄弟节点群(链表)
BROTHER CreateBrothers(BROTHER brothers,char *brotherset)   //若干个节点构成兄弟
{
    char *p=brotherset;                                     //多个节点，分隔符'/'
    NODE node;
    CreateStr(brotherset);                                  //变成多个字符串
    while(*p)
    {
        //Set(Node,p,setvalue);
        strcpy(node,p);
        brothers=Add_A_Brother(brothers,node);              //加入兄弟关系中
        p+=strlen(node)+1;                                  //下一个节点
    }
    return brothers;                                        //返回兄弟节点链表
}

//2.2.10 根据树文件建立树
//树文件为txt文件，其记录格式为单数行为双亲节点，偶数行为子节点，用字符'/'分隔符分开
TREE CreateTree(TREE tree,char *filename)               //从文件创建树
{
    TREE subtree;
    BROTHER brothers;
    FILE *fp;
    char parent[200],brotherset[5000];
    fp=fopen(filename,"r");
    while(!feof(fp))                                     //文件中是否还存在树的节点名称
    {
        fscanf(fp,"%s",parent);                          //读入双亲节点
        fscanf(fp,"%s",brotherset);                      //读入若干兄弟节点(子节点)，分隔符'/'
        //fgetc(fp);
        //fgets(brotherset,100,fp);
        brothers=NULL;
        brothers=CreateBrothers(brothers,brotherset);    //构建双亲节点
        subtree=Form_Pa_Ch(parent,brothers);             //构建子树
        tree=Add_A_Sub_Tree(tree,subtree);                //树中加入子树
    }
    fclose(fp);                                          //关闭文件
    return tree;                                         //返回所建的树
}

//2.3 树搜索实现
//2.3.1 复制子节点集
//复制所有节点（链表），返回复制结果的头指针，建立链式队列
BROTHER CopyBrothers(BROTHER children)                       //节点集复制
{
    BROTHER copynode,lastnode,head=NULL;                     //没有子节点
    while(children)
    {
        copynode=(BROTHER)malloc(sizeof(struct BROTHERNODE));
        //Set(copynode->node,cildren->node,SetValue);
        strcpy(copynode->node,children->node);               //复制节点
        copynode->next=NULL;
        if(head==NULL)
        {
            head=copynode;                                   //第1个节点
        }
        else
        {
            lastnode->next=copynode;                         //非第1个节点：建立链接，复制子节点集
        }
        lastnode=copynode;
        children=children->next;                             //下一个子节点
    }
    return head;                                             //返回头节点指针
}

//2.3.2 扩展节点集
//根据树结构从双亲节点中找到所有孩子节点(兄弟节点)，并复制所有孩子节点，最后返回所有复制结果的头指针
BROTHER ExpandNodes(TREE tree,NODE pa)              //由节点获取所有子节点
{
    BROTHER children=NULL;                          //孩子节点
    TREE t=tree;                                    //树
    while(t)                                        //节点不为空
    {
        //if(Equal(t->node.node,pa,EqualFun)==0)
        if(strcmp(t->node.node,pa)==0)              //找到分支节点
        {
            children=CopyBrothers(t->node.children);
            break;
        }
        t=t->next;                                  //下一个双亲结点
    }
    return children;
}

//2.3.3 所有节点进栈
//将所有节点进栈并返回堆栈指针//
typedef struct BROTHERNODE *STACK;              //定义堆栈类型，实际上也是节点链表【兄弟节点链表】
STACK PushChildren(STACK stack,BROTHER children)//所有节点进栈
{
    BROTHER p,head;
    head=CopyBrothers(children);                //复制所有孩子节点
    p=head;                                     //复制节点并入堆栈
    if(p!=NULL)                                 //存在孩子节点
    {
        while(p->next)  p=p->next;              //指向最后节点
        p->next=stack;                          //链表连接
        stack=head;
    }
    return stack;
}

//2.3.4 出栈与回收堆栈
STACK Pop_A_Child(STACK stack,NODE child)  //出栈
{
    STACK p=stack;
    if(p!=NULL)                            //堆栈不为空
    {
        //Set(child,p->node,SetValue);
        strcpy(child,p->node);             //获取节点名称
        stack=p->next;                     //堆栈后移
        free(p);                           //回收节点单元
    }
    return stack;                          //返回堆栈头指针
}

STACK ClearStack(STACK stack)              //回收栈空间
{
    stack=(STACK)ClearBrothers((BROTHER)stack);   //清除所有节点，得到空指针
    return stack;                          //返回空指针
}

//2.3.5 可回溯、盲目、深度优先搜索
#define TRUE 1                              //定义符号常量“真”
#define FALSE 0                             //定义符号常量“假”
typedef int STATUS;                         //定义状态类型，表示“真”或“假”

//2.5 树搜索（递归）
//2.5.1 定位子树位置
TREE GetSubTree(TREE tree,NODE pa)                      //由结点获取所有子结点
{
    TREE subtree=tree;
    while(subtree)                                      //从树存储结构中遍历每颗子树
    {
        if(strcmp(subtree->node.node,pa)==0)  break;    //找到子树
        //if(Equal(subtree->node.node,pa)==0) break;
        else subtree=subtree->next;                     //下一棵子树
    }
    return subtree;                                     //返回子树
}

//2.5.2 基于递归搜索子树
STATUS SearchSubTreeRe(TREE tree,TREE subtree,NODE end)   //判断节点是否在树中，深度优先递归搜索
{
    TREE subsubtree;                                    //子树的子树（树根）
    BROTHER children;                                   //所有子节点
    STATUS flag=FALSE;                                  //目标节点是否再树中标识
    if(subtree==NULL) return flag;                      //子树为空树，目标节点不在树中
    if(strcmp(subtree->node.node,end)==0)               //子树树根是目标节点
    //if(strcmp(subtree->node.node,end,EqualFun)==0)
    {
        flag=TRUE;
    }
    else                                                //子树树根节点不是目标节点
    {
        children=subtree->node.children;                //子树的所有子节点
        while(children)                                 //依次判断子节点
        {
            subsubtree=GetSubTree(tree,children->node); //得到子节点的子树的子树
            flag=SearchSubTreeRe(tree,subsubtree,end);    //节点取决于是否在子树的子树中
            if(flag==TRUE)  break;                      //若节点在子树的子树中，则就在子树中
            children=children->next;                    //否则，判断其他子节点
        }
    }
    return flag;
}

//2.5.3 搜索树
STATUS Search(TREE tree,NODE start,NODE end)          //判断节点是否在树种，深度优先搜索
{
    TREE subtree;                                     //子树（树根）
    STATUS flag;                                      //目标节点是否在树中标识
    subtree=GetSubTree(tree,start);                   //得到子树
    if(subtree) flag=SearchSubTreeRe(tree,subtree,end); //搜索子树，判断目标存在性
    return flag;                                      //返回目标节点是否以节点start开始的子树中
}

//2.5.M 树搜索（递归）部分主程序
//void SearchPartRecurrence()
int main()
{
    NODE start,end;                                                  //子树根节点、目标节点
    TREE tree;                                                       //链式存储结构树
    STATUS flag;                                                     //目标是否在子树中标识
    char *filename="D:\\Develop\\C-Main\\DS_LiGuohe\\Chapter2\\Chapter2.txt";  //树结构文件
    tree=CreateTree(tree,filename);                                  //创建链式存储结构树
    printf("The Start Node:");
    scanf("%s",start);                                               //输入子树根节点名称
    printf("The End Node:");
    scanf("%s",end);                                                 //输入目标节点名称
    flag=Search(tree,start,end);                                     //判断节点end是否在以节点start为根的子树中
    printf("Search %s from %s,Status=%d\n",end,start,flag);          //输出是否存在的标识
    printf("===========\n");
    ClearTree(tree);                                                 //回收树空间
}